A travel route between an origin location and a destination location may be determined by a computer system, which may be referred to as a mapping system. The mapping system may make this determination by searching for an optimal path through a directed graph (e.g., a collection of nodes and edges) that represents a network of roads and intersections. Each edge (or link) of the graph may represent a road in a map, and each node of the graph may represent an intersection of two or more roads or a terminal point of a road, such as a dead end road. A user of a mapping system may want to see driving directions, which may be in the form of maneuvers in the travel route with a narrative description of each maneuver to be made.